package com.cat.binaryTree;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/
 * @create 2025/9/11 21:21
 * @since JDK17
 */

public class Solution16 {
    int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode p = head, pre;
        while (p.next != null) {
            pre = p;
            p = p.next;
            ListNode q = new ListNode(gcd(pre.val, p.val));
            pre.next = q;
            q.next = p;
        }
        return head;
    }
}
